Pronalaženje velikih pseudoprostih brojeva korišćenjem Miller - Rabin algoritma

Probabilistički algoritam Las Vegas tipa za pronalaženje pseudoslučajnih brojeva pomoću probabilističkog Miller - Rabin testa

import random

# Pomocne funkcije
def mod_pow(a, n, m):
    result = 1
    a = a % m
    while n > 0:
        if n % 2 == 1:
            result = (result * a) % m
        a = (a * a) % m
        n = n // 2
        
    return result

def miller_rabin(n, k):
    if n <= 3:
        if n == 1:
            return False
        return True
  
    # n prost => n neparan => n = (2 ^ r) * d + 1
    d = n - 1
    r = 0
    while d % 2 == 0:
        r = r + 1
        d = d // 2
        
    for i in range(k):
        a = random.randrange(2, n - 1)
        
        x = mod_pow(a, d, n)

        if x == 1 or x == n - 1:
            continue
            
        wittness = True
        
        for j in range(r - 1):
            x = mod_pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1: # n - 1 = -1 (mod n)
                wittness = False
                break
        
        if wittness:
            return False
    return True


def get_prime(limit, k = 20):
    is_prime = False
    while not is_prime:
        n = random.randrange(limit)
        is_prime = miller_rabin(n, k)
    return n

get_prime(2**256)

71300625213881960432373910767241076098777021985410310187782794252803940846787